Server and desktop virtualization is dramatically changing the enterprise network by creating many “virtual networks” which connect virtual machines and the physical networks through virtual switches. In this new network paradigm, many new network services requirements are imposed on modern IT network infrastructure. For example, in a virtual network, inter-virtual machine (VM) communication is a blind spot because this traffic never reaches the physical network, making it unprotected by a physical network security appliance. The absence of protection in a virtual network becomes a key security concern in a virtualized data center, especially in a multi-tenant cloud service provider data center environment where it is required to deploy a virtual service that serves as a segmentation firewall for all the managed virtual machines.